package leetcode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Lc127_2 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        HashSet<String> wordSet = new HashSet<>();
        for (int i = 0; i < wordList.size(); i++) {
            wordSet.add(wordList.get(i));
        }
        HashSet<String> visited = new HashSet<>();
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                String word = queue.poll();
                char[] charArr = word.toCharArray();
                for (int i = 0; i < charArr.length; i++) {
                    char origin = charArr[i];
                    for (char x = 'a'; x <= 'z' ; x++) {
                        if (x == origin) continue;
                        charArr[i] = x;
                        String newWord = new String(charArr);
                        if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                            if (endWord.equals(newWord))
                                return step + 1;
                            queue.offer(newWord);
                            visited.add(newWord);
                        }
                    }
                    charArr[i] = origin;
                }
            }
            step ++;
        }
        return 0;
    }



}
